package com.gyg.程序员面试金典;

/**
 * 面试题 04.01. 节点间通路
 * 节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
 *解题思路：采用递归，逐步缩小查询的路径长度
 * （1）判断路径的起始点和终点是否是同一个，如果是就直接返回true
 * （2）遍历存放路径节点的数组，将每一段路径的尾节点和查询路径的尾节点对比，看查询路径的终点是否是某一段路径的终点，如果不是就返回false
 * （3）如果查询路径的终点是某一段路径的终点，那么判断查询路径的起点是否是该段路径的起点
 * （4）如果查询路径的起点是该段路径的起点，那么说明这一段路径和要查询的路径重合
 * （5）如果查询路径的起点不是该段路径的起点，那么我们可以查找从start到该段路径的起点是否存在通路即可
 */
public class T04_01 {
    /**
     * @param n      节点数
     * @param graph  连接点的数组
     * @param start  要查询的路径的起始点
     * @param target 要查询的路径的终点
     * @return 是否存在这样的通路
     */
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
//        （1）判断路径的起始点和终点是否是同一个，如果是就直接返回true
        if (start == target) {
            return true;
        }
//        （2）遍历存放路径节点的数组，将每一段路径的尾节点和查询路径的尾节点对比，
//        看查询路径的终点是否是某一段路径的终点，如果不是就返回false
        for (int[] oneGreaph : graph) {
//            （3）如果查询路径的终点是某一段路径的终点，那么判断查询路径的起点是否是该段路径的起点
            if (oneGreaph[1] == target){
//                （4）如果查询路径的起点是该段路径的起点，那么说明这一段路径和要查询的路径重合
                if (oneGreaph[0] == start){
                    return true;
                }else {
//                （5）如果查询路径的起点不是该段路径的起点，那么我们可以查找从start到该段路径的起点是否存在通路即可
                    return findWhetherExistsPath(n, graph, start, oneGreaph[0]);
                }
            }
        }

        return false;
    }
}
